/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author TuanND
 */
public class Percolation {

    private int N;
    private boolean sites[][];
    private WeightedQuickUnionUF uf;

    public Percolation(int N) // create N-by-N grid, with all sites blocked
    {
        this.N = N;
        sites = new boolean[N][N];
        uf = new WeightedQuickUnionUF(N * N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sites[i][j] = false;
            }
        }
    }

    public void open(int i, int j) // open site (row i, column j) if it is not already
    {
        if (!isOpen(i, j)) {
            sites[i][j] = true;
            if ((i > 0) && isOpen(i - 1, j)) {
                uf.union((i - 1) * N + j, i * N + j);
            }
            if ((i < (N - 1)) && isOpen(i + 1, j)) {
                uf.union(i * N + j, (i + 1) * N + j);
            }
            if ((j > 0) && isOpen(i, j - 1)) {
                uf.union(i * N + j - 1, i * N + j);
            }
            if ((j < (N - 1)) && isOpen(i, j + 1)) {
                uf.union(i * N + j, i * N + j + 1);
            }
        }
    }

    public boolean isOpen(int i, int j) // is site (row i, column j) open?
    {
        return sites[i][j];
    }

    public boolean isFull(int i, int j) // is site (row i, column j) full?
    {
        boolean isFull = false;
        int o = uf.find(i * N + j);
        for (int k = 0; k < N; k++) {
            int o_k = uf.find(k);
            if (o_k == o){
                isFull = true;
                break;
            }
        }
        return isFull;
    }

    public boolean percolates() // does the system percolate?
    {
        boolean isPercolate = false;
        for (int j = 0; j < N; j++){
            if (isFull(N-1,j)){
                isPercolate = true;
                break;
            }
        }
        return isPercolate;
    }
}
